package interviewClassic150;

import java.util.*;

public class RandomizedSet {
    private Map<Integer,Integer> value2index;
    //一个list集合
    private List<Integer> list;
    Random random;

    public RandomizedSet() {
        this.value2index = new HashMap<>();
        this.list = new ArrayList<>();
        this.random = new Random();
    }

    public boolean insert(int val) {
        //判断值在集合中是否存在
        if (value2index.containsKey(val)) return false;
        //不存在，则插入
        list.add(val);
        int insertIndex = list.size() - 1;
        value2index.put(val,insertIndex);
        return true;
    }

    public boolean remove(int val) {
        //根据val查询是否存在
        if (!value2index.containsKey(val)) return false;
        //存在，则去删除元素，找到这个元素的index，将数组最后一个元素放到那个位置，重设最后一个元素的位置信息
        int removeIndex = value2index.get(val);
        int lastElement = list.get(list.size() - 1);
        list.set(removeIndex,lastElement);
        value2index.put(lastElement,removeIndex);
        list.remove(list.size() - 1);
        //map也移除对应元素
        value2index.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = this.random.nextInt(list.size());
        return list.get(randomIndex);
    }
}
